import java.math.*;
import java.util.Arrays;
import java.util.Scanner;

class Solute{
    int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if((sum + target) % 2 == 1 || sum < Math.abs(target)){
            return 0;
        }
        int add = (sum + target) / 2;
        System.out.println(add);

        int[][] dp = new int[nums.length][add + 1];
        for (int[] tmp : dp) {
            for (int x : tmp) {
                System.out.print(x + " ");
            }
            System.out.println();
        }

        //初始化dp数组
        for(int i = 0; i <= add; i++){
            if(i == nums[0]){
                dp[0][i] = 1;
            }
        }
        for (int i = 0; i < add + 1; i++) {
            System.out.print(dp[0][i] + " ");
        }
        System.out.println();
        System.out.println();

        if(nums[0] == 0) dp[0][0] = 2;
        else dp[0][0] = 1;
        //打印第一行
        for (int i = 0; i < add + 1; i++) {
            System.out.print(dp[0][i] + " ");
        }
        System.out.println();

        //填写dp数组
        for(int i = 1; i < nums.length; i++){
            for(int j = 0; j <= add; j++){
                if(nums[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                }
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j-nums[i]];
                }
            }
        }

        for (int[] tmp : dp) {
            for (int x : tmp) {
                System.out.print(x + " ");
            }
            System.out.println();
        }

        return dp[nums.length - 1][add];
    }
}
//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.MIN_VALUE);
    }
    public static void main3(String[] args) {
        int[] nums = {1,1,1,1,1};
        int target = 3;
        findTargetSumWays(nums, target);
    }

    public static int findTargetSumWays(int[] nums, int target) {

        // 01背包应用之“有多少种不同的填满背包最大容量的方法“
        // 易于理解的二维数组解法及详细注释

        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        // 注意nums[i] >= 0的题目条件，意味着sum也是所有nums[i]的绝对值之和
        // 这里保证了sum + target一定是大于等于零的，也就是left大于等于零（毕竟我们定义left大于right）
        if(sum < Math.abs(target)){
            return 0;
        }

        // 利用二元一次方程组将left用target和sum表示出来（替换掉right组合），详见代码随想录对此题的分析
        // 如果所求的left数组和为小数，则作为整数数组的nums里的任何元素自然是没有办法凑出这个小数的
        if((sum + target) % 2 != 0) {
            return 0;
        }

        int left = (sum + target) / 2;

        // dp[i][j]：遍历到数组第i个数时， left为j时的能装满背包的方法总数
        int[][] dp = new int[nums.length][left + 1];

        // 初始化最上行（dp[0][j])，当nums[0] == j时（注意nums[0]和j都一定是大于等于零的，因此不需要判断等于-j时的情况），有唯一一种取法可取到j，dp[0][j]此时等于1
        // 其他情况dp[0][j] = 0
        // java整数数组默认初始值为0
        if (nums[0] <= left) {
            dp[0][nums[0]] = 1;
        }

        // 初始化最左列（dp[i][0])
        // 当从nums数组的索引0到i的部分有n个0时（n > 0)，每个0可以取+/-，因此有2的n次方中可以取到j = 0的方案
        // n = 0说明当前遍历到的数组部分没有0全为正数，因此只有一种方案可以取到j = 0（就是所有数都不取）
        int numZeros = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                numZeros++;
            }
            dp[i][0] = (int) Math.pow(2, numZeros);

        }

        // 递推公式分析：
        // 当nums[i] > j时，这时候nums[i]一定不能取，所以是dp[i - 1][j]种方案数
        // nums[i] <= j时，num[i]可取可不取，因此方案数是dp[i - 1][j] + dp[i - 1][j - nums[i]]
        // 由递推公式可知，先遍历i或j都可
        for(int i = 1; i < nums.length; i++) {
            for(int j = 1; j <= left; j++) {
                if(nums[i] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
                }
            }
        }

         //打印dp数组
         for(int i = 0; i < nums.length; i++) {
             for(int j = 0; j <= left; j++) {
                 System.out.print(dp[i][j] + " ");
             }
             System.out.println("");
         }

        return dp[nums.length - 1][left];

    }

    public static void main6(String[] args) {
        Solute solute = new Solute();
        int[] nums = {1,1,1,1,1};
        int target = 3;
        solute.findTargetSumWays(nums, target);
    }
    public static void main5(String[] args) {
        int[][] dp = new int[5][5];
        for (int i = 0; i < 5; i++) {
            dp[i][0] = 1;
            dp[0][i] = 1;
        }

        for (int[] tmp : dp) {
            for (int x : tmp) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }
    public static void main1(String[] args) {
        //必须先来写一遍最基础的01背包问题
        //之后解决其他题目便游刃有余
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();
        int n = input.nextInt();
        //用一个数组来记录每个物品的重量
        int[] weight = new int[m];
        for (int i = 0; i < m; i++) {
            weight[i] = input.nextInt();
        }

        //用一个数组来记录每个物品的价值
        int[] value = new int[m];
        for (int i = 0; i < m; i++) {
            value[i] = input.nextInt();
        }

        //之后就是利用动态规划，先创建dp数组
        //为了方便理解，我们先不使用滚动数组，也就是一维数组
        int[][] dp = new int[m + 1][n + 1];
        //行是物品，多一个方便使用
        //列是重量

        //之后确定 dp[i][j] 的含义，也就是重量在j的时候放前i个物品的最大价值
        //初始化dp数组
        dp[0][0] = 0;
        //当书包重量为0时，最大价值也就是0
        //当不挑选物品时，能放的最大价值也是0,也就是把0行0列初始化为0
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = 0;
        }

        //我们先遍历物品
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //之后遍历重量
                //先判断当前物品重量是否小于背包重量
                if (weight[i - 1] <= j) {
                    //此时可以放下该物品
                    //我们先以当前重量减去该物品重量
                    //得到该重量后看装上一个物品该重量的最大价值并加上它
                    //之后跟不加该物品也是该重量的价值哪个大，也就是上一行
                    dp[i][j] = Math.max(dp[i - 1][j - weight[i - 1]] + value[i - 1], dp[i - 1][j]);
                } else {
                    //此时背包无法放入当前遍历的物品，直接继承上一行
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        //dp右下角的值就是结果
        System.out.println(dp[m][n]);

    }
}